#pragma once

#include "loirey_GLOBAL.h"
#include "loirey_MyMath.h"

namespace loirey
{
	template<typename T> class CSimpleTypeArray;

	class CDataStructureTools
	{
	public:
		static int InputFromStream(
			istream& inStream, char* pDstData, int MaxCharAmount,
			const char* pSplitChars, const char* pIgnoreChars)
		{
			char op;
			const char* ic;
			const char* sc;
			int ret = 0;
			for ( ; ; )
			{
				if (ret >= MaxCharAmount)
				{ op = 2; break; }

				inStream.read(&op, 1);
				if (op==0 || inStream.eof())
				//if (!(inStream>>op))
				{ op = 0; break; }

				for ( sc = pSplitChars; *sc && op!=*sc; ++sc );
				for ( ic = pIgnoreChars; *ic && op!=*ic; ++ic );

				if ((op==*sc) && ((op!=*ic) || (ret>0)))
				{ op = 1; break; }

				if (op!=*ic)
				{
					++ret;
					*(pDstData++) = op;
				}
			}
			*pDstData = 0;
			if (op==0 && ret==0)
				return -1;
			else
				return ret;
		}
		static int InputFromStream(
			istream& inStream, string& DstData,
			const char* pSplitChars, const char* pIgnoreChars)
		{
			static char strTemp[100001];
			int ret = InputFromStream(inStream, strTemp, 100000, pSplitChars, pIgnoreChars);
			DstData = strTemp;
			return ret;
		}

		template<typename T>
		static size_t my_fread(FILE* FIN, T* dst_data, size_t length)
		{
			if (FIN == NULL) return 0;

			size_t MAX_WRITING_LENGTH = ((size_t)1048576) * (size_t)1024 / sizeof(*dst_data);
			if (MAX_WRITING_LENGTH < 1) MAX_WRITING_LENGTH = 1;
			size_t ret, tt;

			ret = 0;
			while (length > MAX_WRITING_LENGTH)
			{
				tt = fread(dst_data, sizeof(*dst_data), MAX_WRITING_LENGTH, FIN);
				ret += tt; if (tt < MAX_WRITING_LENGTH) return ret;
				dst_data += MAX_WRITING_LENGTH;
				length -= MAX_WRITING_LENGTH;
			}
			ret += fread(dst_data, sizeof(*dst_data), length, FIN);
			return ret;
		}
		template<typename T>
		static size_t my_fwrite(FILE* FOUT, const T* src_data, size_t length)
		{
			if (FOUT == NULL) return 0;

			size_t MAX_WRITING_LENGTH = ((size_t)1048576) * (size_t)1024 / sizeof(*src_data);
			if (MAX_WRITING_LENGTH < 1) MAX_WRITING_LENGTH = 1;
			size_t ret, tt;

			ret = 0;
			while (length > MAX_WRITING_LENGTH)
			{
				tt = fwrite(src_data, sizeof(*src_data), MAX_WRITING_LENGTH, FOUT);
				ret += tt; if (tt < MAX_WRITING_LENGTH) return ret;
				src_data += MAX_WRITING_LENGTH;
				length -= MAX_WRITING_LENGTH;
			}
			ret += fwrite(src_data, sizeof(*src_data), length, FOUT);
			return ret;
		}

		template<typename T>
		static bool my_fread_single(FILE* FIN, T& DstData)
		{
			return (my_fread(FIN, &DstData, 1) == 1);
		}
		template<typename T>
		static bool my_fwrite_single(FILE* FOUT, const T& SrcData)
		{
			return (my_fwrite(FOUT, &SrcData, 1) == 1);
		}

		template<typename T>
		static size_t my_fread(FILE* FIN, CSimpleTypeArray<T>& DstList, size_t Size)
		{
			DstList.Resize(Size);
			return my_fread(FIN, DstList.pElement, Size);
		}
		template<typename T>
		static size_t my_fwrite(FILE* FOUT, const CSimpleTypeArray<T>& SrcList, size_t Size)
		{
			if (Size > SrcList.Size) Size = SrcList.Size;
			return my_fwrite(FOUT, SrcList.pElement, Size);
		}
		template<typename T>
		static size_t my_fread(FILE* FIN, CSimpleTypeArray<T>& DstList)
		{
			return my_fread(FIN, DstList.pElement, DstList.Size);
		}
		template<typename T>
		static size_t my_fwrite(FILE* FOUT, const CSimpleTypeArray<T>& SrcList)
		{
			return my_fwrite(FOUT, SrcList.pElement, SrcList.Size);
		}

		template<typename T>
		static void MyRelease_List(T*& a)
		{
			if (a != NULL) 
			{
				delete[] a;
				a = NULL;
			}
		}
		template<typename T>
		static void MyRelease_Single(T*& a)
		{
			if (a != NULL) 
			{
				delete a;
				a = NULL;
			}
		}
		template<typename TSimpleValueType>
		static void ReleasePointers(CSimpleTypeArray<TSimpleValueType*>& SimpleValuePointerList)
		{
			size_t i;
			TSimpleValueType** ptr = SimpleValuePointerList.pElement;
			for ( i = 0; i < SimpleValuePointerList.Size; ++i )
			{
				delete *ptr;
				*ptr = NULL;
				++ptr;
			}
			SimpleValuePointerList.Clear();
		}
		template<typename TSimpleValueType>
		static void LoadSimpleTypeArray(CSimpleTypeArray<TSimpleValueType>& DstDataList, FILE* FIN)
		{
			size_t len;
			if (my_fread_single(FIN, len))
				my_fread(FIN, DstDataList, len);
		}
		template<typename TSimpleValueType>
		static void SaveSimpleTypeArray(FILE* FOUT, const CSimpleTypeArray<TSimpleValueType>& SrcDataList)
		{
			size_t len = SrcDataList.Size;
			if (my_fwrite_single(FOUT, len))
				my_fwrite(FOUT, SrcDataList);
		}
		template<typename TSimpleValueType>
		static void LoadSimpleTypeArray(CSimpleTypeArray<TSimpleValueType>& DstDataList, string strFN_SrcDataList)
		{
			FILE* FIN = fopen(strFN_SrcDataList.c_str(), "rb");
			LoadSimpleTypeArray(DstDataList, FIN);
			if (FIN) fclose(FIN);
		}
		template<typename TSimpleValueType>
		static void SaveSimpleTypeArray(string strFN_DstDataList, const CSimpleTypeArray<TSimpleValueType>& SrcDataList)
		{
			FILE* FOUT = fopen(strFN_DstDataList.c_str(), "wb");
			SaveSimpleTypeArray(FOUT, SrcDataList);
			if (FOUT) fclose(FOUT);
		}

		static int Hex2Num(char ch)
		{
			if (ch>='0' && ch<='9') return ch - '0';
			if (ch>='a' && ch<='f') return ch - 'a' + 10;
			if (ch>='A' && ch<='F') return ch - 'A' + 10;
			return -1;
		}

		static void ToUpperCase(char* dstStr)
		{
			for ( ; *dstStr; ++dstStr )
				if (*dstStr>='a' && *dstStr<='z')
					*dstStr += 'A' - 'a';
		}
		static void ToLowerCase(char* dstStr)
		{
			for ( ; *dstStr; ++dstStr )
				if (*dstStr>='A' && *dstStr<='Z')
					*dstStr += 'a' - 'A';
		}
		static void ToUpperCase(string& dstStr)
		{
			int i;
			for ( i = (int)dstStr.length()-1; i >= 0; --i )
				if (dstStr[i]>='a' && dstStr[i]<='z')
					dstStr[i] += 'A' - 'a';
		}
		static void ToLowerCase(string& dstStr)
		{
			int i;
			for ( i = (int)dstStr.length()-1; i >= 0; --i )
				if (dstStr[i]>='A' && dstStr[i]<='Z')
					dstStr[i] += 'a' - 'A';
		}
	};

	class CComparableObject
	{
	public:
		virtual int Compare(const CComparableObject& b) const = 0;

	public:
		virtual bool operator < (const CComparableObject& b) const;
		virtual bool operator <= (const CComparableObject& b) const;
		virtual bool operator > (const CComparableObject& b) const;
		virtual bool operator >= (const CComparableObject& b) const;
		virtual bool operator != (const CComparableObject& b) const;
		virtual bool operator == (const CComparableObject& b) const;
	};

	class CHistogramConfig
	{
	public:
		int BinAmount;
		double ValueBinWidth;
		double ValueBase;
		//int BinSelectMode;
		bool fAreBinWrapped;
	public:
		void myInit(int BinAmount, bool fAreBinWrapped, double ValueBoundA, double ValueBoundB);
	public:
		bool InputFromStream(istream& inStream);
		void OutputToStream(ostream& outStream) const;
	public:
		double GetBinMiddleValue(int BinIndex) const;
		double GetBinFloorValue(int BinIndex) const;
		double GetBinCeilingValue(int BinIndex) const;
		int SetBinIndexCorrect(int BinIndex) const;
		int SelectBin_LowerThan(double Value) const;
		int SelectBin_GreaterThan(double Value) const;
		int SelectBin_Nearest(double Value) const;
		double SelectBin_Bounding(int& BinA, int& BinB, double Value) const;
	};

	class CBoundedValueHistogram
	{
	public:
		static const int INTERPOLATING_TYPE_SINGLE_BIN = 1;
		static const int INTERPOLATING_TYPE_DOUBLE_BIN_LINEAR = 2;
	public:
		int Mode;
		int BinAmount;
		double* pBinWeight;
		double WeightSum;
		double ValueBase;
		double ValuePerBin;

	public:
		CBoundedValueHistogram();
		void myInit(int BinAmount, double* pBinWeight);
		void SetParameters(int Mode, double ValueBound_A, double ValueBound_B);
		void Clear();
		int		SetIndexBounded(int Index);
		double	GetThreshold_SmallerThan(int BinIndex);
		double	GetThreshold_BiggerThan(int BinIndex);
		int		GetIndex_Floor(double Value);
		double	GetIndex_Between(double Value, int& i, int& j);
		void PushValue(double Value, double Weight);
		void CalcWeightSum();
		void LetEquals(const CBoundedValueHistogram& b);
		void AddEquals(const CBoundedValueHistogram& b);
		void SubEquals(const CBoundedValueHistogram& b);
		void MulEquals(const CBoundedValueHistogram& b);
		void MulEquals(double num);
	};

	template<typename T>
	class CBinaryItemSegmentTree
	{
	protected:
		int _n;
		T* _pCumulant;

	protected:
		void myRelease()
		{
			_n = 0;
			CDataStructureTools::MyRelease_List(_pCumulant);
		}
	public:
		CBinaryItemSegmentTree()
		{
			_n = 0;
			_pCumulant = NULL;
		}
		~CBinaryItemSegmentTree()
		{
			myRelease();
		}
		void myInit(int NodeAmount)
		{
			myRelease();

			_n = NodeAmount;
			_pCumulant = new T[_n+1];
			Clear();
		}
		void Clear()
		{
			int i;
			T* ptr;
			for ( ptr = _pCumulant, i = 0; i <= _n; ++i, ++ptr )
				*ptr = (T)0;
		}
		void AddToNode(int NodeIndex, const T& Value)
		{
			if (NodeIndex<0) return;
			++NodeIndex;
			while (NodeIndex<=_n)
			{
				_pCumulant[NodeIndex] += Value;
				NodeIndex += NodeIndex & (NodeIndex ^ (NodeIndex-1));
			}
		}
		T GetCumulativeSum(int NodeIndex)
		{
			T ret = (T)0;
			++NodeIndex;
			while (NodeIndex>0)
			{
				if (NodeIndex<=_n)
					ret += _pCumulant[NodeIndex];
				NodeIndex -= NodeIndex & (NodeIndex ^ (NodeIndex-1));
			}
			return ret;
		}
	};

	class CUnionSet
	{
	protected:
		int _n;
		int* _rgParent;
		CBinaryItemSegmentTree<int> _root_index;
		
	protected:
		void myRelease();
	public:
		CUnionSet();
		~CUnionSet();
		
		void myInit(int NodeAmount);

		void Clear();
		void Merge(int NodeIndexA, int NodeIndexB);
		int GetRootAmount();
		int FindRoot(int NodeIndex);
		int GetRootIndex(int NodeIndex);
	};

	template<typename TLabel, typename TValue>
	class CLabelValueMapping
	{
	public:
		typedef map<TLabel, TValue> CMap;
		typedef typename CMap::iterator CIterator;
	public:
		CMap Mapping;

	public:
		void Clear() { Mapping.clear(); }
		CLabelValueMapping() { Clear(); }
		size_t Size() { return Mapping.size(); }
		CIterator GetIterator(const TLabel& Label)
		{
			CMap::iterator itr = Mapping.find(Label);
			if (itr == Mapping.end())
			{
				Mapping[Label] = (TValue)0.0;
				itr = Mapping.find(Label);
			}
			return itr;
		}
		const TValue& AddTo(const TLabel& Label, const TValue& Value)
		{
			CIterator itr = GetIterator(Label);
			itr->second += Value;
			return itr->second;
		}
		const TValue& GetValue(const TLabel& Label)
		{
			CIterator itr = Mapping.find(Label);
			if (itr == Mapping.end())
				return 0.0;
			else
				return itr->second;
		}
	};

	template<typename T>
	class CSimpleDictionary
	{
	protected:
		typedef map<T, int> CDictMap;
		typedef typename CDictMap::iterator CIterator;
	protected:
		int _n;
		CDictMap _map;
		vector<const T*> _v;
	public:
		T DefaultValue;

	public:
		void Clear()
		{
			_n = 0;
			_map.clear();
			_v.clear();
		}
		CSimpleDictionary()
		{
			Clear();
		}
		int GetID_Const(const T& Value) const
		{
			int ret = -1;
			CDictMap::const_iterator itr = _map.find(Value);
			if (itr != _map.end())
				ret = itr->second;
			return ret;
		}
		int GetID(const T& Value, bool fInsertIfNeed)
		{
			int ret = -1;
			CDictMap::iterator itr = _map.find(Value);
			if (itr != _map.end())
				ret = itr->second;
			else if (fInsertIfNeed)
			{
				_map[Value] = _n;
				itr = _map.find(Value);
				_v.push_back(&(itr->first));
				ret = _n++;
			}
			return ret;
		}
		const T* GetValue(int ID) const
		{
			if (ID<0 || ID>=_n)
				return &DefaultValue;
			else
				return _v[ID];
		}
		int Size() const
		{
			return _n;
		}
	};

	template<typename TSimpleType>
	class CSimpleTypeArray
	{
	private:
		size_t __bufSize;
	protected:
		TSimpleType _DefaultValue;
	public:
		size_t Size;
		TSimpleType* pElement;

	protected:
		void myRelease()
		{
			__bufSize = 0;
			Size = 0;
			CDataStructureTools::MyRelease_List(pElement);
		}
	public:
		CSimpleTypeArray(const TSimpleType& DefaultValue = TSimpleType())
		{
			_DefaultValue = DefaultValue;
			__bufSize = 1;
			Size = 0;
			pElement = new TSimpleType [1];
		}
		CSimpleTypeArray(const CSimpleTypeArray<TSimpleType>& b)
		{
			//cout<<"C"<<endl;

			__bufSize = (b.Size<1 ? 1 : b.Size);
			//__bufSize = b.__bufSize;
			Size = 0;
			pElement = new TSimpleType [(size_t)__bufSize];

			CloneByValue(b);
		}
		CSimpleTypeArray& operator = (const CSimpleTypeArray<TSimpleType>& b)
		{
			//cout<<"="<<endl;
			if (this == &b) return *this;
			myRelease();

			__bufSize = (b.Size<1 ? 1 : b.Size);
			//__bufSize = b.__bufSize;
			Size = 0;
			pElement = new TSimpleType [(size_t)__bufSize];

			CloneByValue(b);
			return *this;
		}
		~CSimpleTypeArray()
		{
			myRelease();
		}
		void CloneByValue(const CSimpleTypeArray<TSimpleType>& b)
		{
			size_t i;

			Resize(b.Size);
			for ( i = 0; i < Size; ++i )
				pElement[i] = b.pElement[i];
		}
		void CloneByPointer(const CSimpleTypeArray<TSimpleType>& b)
		{
			if (&b == this) return;
			myRelease();
			__bufSize = b.__bufSize;
			Size = b.Size;
			pElement = b.pElement;
		}
		size_t GetRealSize() const
		{
			return __bufSize;
		}
		size_t GetMemoryUsage() const
		{
			return sizeof(TSimpleType) * (__bufSize + 1) + sizeof(size_t) * 2 + sizeof(TSimpleType*);
		}
		void Resize(size_t NewSize)
		{
			Resize(NewSize, _DefaultValue);
		}
		void ToBeTight()
		{
			__bufSize = (Size<1 ? 1 : Size);
			TSimpleType* _tmpData = new TSimpleType [__bufSize];
			if (pElement != NULL)
			{
				size_t i;
				TSimpleType* pd = _tmpData;
				const TSimpleType* qd = pElement;
				for ( i = 0; i < Size; ++i )
					*(pd++) = *(qd++);
					//_tmpData[i] = pElement[i];
				delete[] pElement;
			}
			pElement = _tmpData;
		}
		void Resize(size_t NewSize, const TSimpleType& DefaultValue)
		{
			if (NewSize > Size)
			{
				size_t i;
				TSimpleType* pd;
				const TSimpleType* qd;

				if (NewSize > __bufSize)
				{
					size_t SG = (size_t)1048576 / sizeof(TSimpleType) * (size_t)512;
					if (__bufSize + __bufSize <= SG)
						__bufSize += __bufSize;
					else
						__bufSize += __bufSize / 2;
					if (__bufSize < NewSize)
						__bufSize = NewSize;

					TSimpleType* _tmpData = new TSimpleType [__bufSize];
					if (pElement != NULL)
					{
						pd = _tmpData;
						qd = pElement;
						for ( i = 0; i < Size; ++i )
							*(pd++) = *(qd++);
							//_tmpData[i] = pElement[i];
						//memcpy(_tmpData, pElement, sizeof(TSimpleType) * Size);
						//free(pElement);
						delete[] pElement;
					}
					pElement = _tmpData;
				}
				pd = pElement + Size;
				for ( i = Size; i < NewSize; ++i )
					*(pd++) = DefaultValue;
					//pElement[i] = DefaultValue;
			}
			Size = (NewSize<0 ? 0 : NewSize);
		}
		void Reserve(size_t BufSize)
		{
			size_t o = Size;
			if (BufSize > o)
			{
				Resize(BufSize);
				Resize(o);
			}
		}
		void Fill(const TSimpleType& Value)
		{
			size_t i;
			TSimpleType* pd = pElement;
			for ( i = 0; i < Size; ++i )
				*(pd++) = Value;
				//pElement[i] = Value;
		}
		void Assign(const TSimpleType* pSrcData, size_t ListLength)
		{
			this->Resize(ListLength);
			this->Clear();
			for ( ; ListLength > 0; --ListLength )
				PushBack(*(pSrcData++));
		}
		TSimpleType& GetRefElement(int Index)
		{
			return pElement[Index];
		}
		TSimpleType* GetPtrElement(int Index)
		{
			return pElement+Index;
		}
		const TSimpleType& GetRefElement(int Index) const
		{
			return pElement[Index];
		}
		const TSimpleType* GetPtrElement(int Index) const
		{
			return pElement+Index;
		}
		void Clear()
		{
			Resize(0);
		}
		void DeepClear()
		{
			if (__bufSize < 2)
				Clear();
			else
			{
				myRelease();
				__bufSize = 1;
				Size = 0;
				pElement = new TSimpleType[1];
			}
		}
		void PushBack(const TSimpleType& Value)
		{
			Resize(Size+1, Value);
		}
		void PushBack(const TSimpleType* List, size_t Amount)
		{
			size_t i;
			size_t s = this->Size;
			Resize(s + Amount);
			TSimpleType* dst = pElement + s;
			for ( i = 0; i < Amount; ++i )
				*(dst++) = *(List++);
		}
		void PushBack(const CSimpleTypeArray<TSimpleType>& List, size_t Amount)
		{
			if (Amount > List.Size) Amount = List.Size;
			PushBack(List.pElement, Amount);
		}
		void PushBack(const CSimpleTypeArray<TSimpleType>& List)
		{
			PushBack(List, List.Size);
		}
		const TSimpleType& PopBack()
		{
			Resize(Size-1);
			return pElement[Size];
		}
		TSimpleType* Begin()
		{
			return pElement;
		}
		TSimpleType* End()
		{
			return pElement + Size;
		}
		const TSimpleType* Begin() const
		{
			return pElement;
		}
		const TSimpleType* End() const
		{
			return pElement + Size;
		}
		void Swap(CSimpleTypeArray<TSimpleType>& Another)
		{
			if (this == &Another) return;
			size_t tst;
			TSimpleType tdv;
			TSimpleType* tpe;
			tst = this->__bufSize; this->__bufSize = Another.__bufSize; Another.__bufSize = tst;
			tst = this->Size; this->Size = Another.Size; Another.Size = tst;
			tdv = this->_DefaultValue; this->_DefaultValue = Another._DefaultValue; Another._DefaultValue = tdv;
			tpe = this->pElement; this->pElement = Another.pElement; Another.pElement = tpe;
		}
		template<typename LengthType>
		void GetPvLenInfo(TSimpleType*& DstPtrValue, LengthType& DstLength)
		{
			DstPtrValue = pElement;
			DstLength = (LengthType)Size;
		}
		template<typename LengthType>
		void GetPvLenInfo(const TSimpleType*& DstPtrValue, LengthType& DstLength) const
		{
			DstPtrValue = pElement;
			DstLength = (LengthType)Size;
		}
		//TSimpleType* NewPlaceAtBack(const TSimpleType& DefaultValue)
		//{
		//	Resize(Size+1, DefaultValue);
		//	return pElement + Size - 1;
		//}
	};

	class CHistogramDistribution
	{
	public:
		int BinAmount;
		CHistogramConfig HistogramConfig;
		CSimpleTypeArray<double> BinWeightDistribution;
		double WeightSum;

	public:
		void InitHistogramConfig(int BinAmount, bool fAreBinWrapped, double ValueBoundA, double ValueBoundB);
	public:
		void Clear();
		void NewWeightedValue(double Value, double Weight = 1.0);
	public:
		double GetBinMiddleValue(int BinIndex) const;
		void Analyse(
			CSimpleTypeArray<double>& BinMiddleValueList,
			CSimpleTypeArray<double>& DistributionList) const;
	};

	class CIVPair
	{
	public:
		int Index;
		double Value;

	public:
		void myInit(int Index, double Value) { this->Index = Index; this->Value = Value; }
		CIVPair() { myInit(0, 0.0); }
		CIVPair(int Index, double Value = 0.0) { myInit(Index, Value); }
	public:
		static bool CompareByIndex(const CIVPair& a, const CIVPair& b);
		static bool CompareByValue(const CIVPair& a, const CIVPair& b);
	};

}

